package demo1;
public class TestDemo {


    //一个先手拿牌,一个后手拿牌,两个人都绝顶聪明
    //两个人都可以从前后拿牌(牌两边都可以拿),哪个人最终获胜,最终返回获胜者的最大分数
    public static int ways1(int[] arr){
        int first = f1(arr,0,arr.length-1);
        int second = g1(arr,0,arr.length-1);
        return Math.max(first,second);
    }

    //在区间[L....R]上先手先拿牌
    public static int f1(int[] arr,int L,int R){
        if(L==R){
            //只剩下一张牌,那只有先手拿到
            return arr[R];
        }
        //否则有两种情况
        //先手拿走左边第一张牌
        int p1 = arr[L] + g1(arr,L+1,R);
        //第二种选择,先手拿走最右边的第一张牌
        int p2 = arr[R] + g1(arr,L,R-1);
        //既然是先手做决定那肯定是拿到两个选择中最大的那个
        return Math.max(p1,p2);
    }

    //后手拿牌---先手先拿牌,先手拿完牌之后--后手就做了先手
    public static int g1(int[] arr,int L,int R){
        if(L==R){
            //如果只剩下一张牌,而又是后手,那就没牌可以选择
            return 0;
        }
        //以下对于拿牌,还是右两种选择
        //第一种选择,先手拿完最左边的牌之后,后手在拿
        int p1 = f1(arr,L+1,R);
        //第二种选择,先手拿走最右边的牌之后,后手在拿
        int p2 = f1(arr,L,R-1);
        return Math.min(p1,p2);//后手拿的牌是先手和后手拿的牌中的最小值
    }

    public static int ways2(int[] arr){
        int N = arr.length;
        int[][] fMap = new int[N][N];
        int[][] gMap = new int[N][N];
        for(int i = 0;i<N;++i){
            for(int j =0;j<N;++j){
                fMap[i][j] = -1;
                gMap[i][j] = -1;
            }
        }
        int first = f2(arr,0,arr.length-1,fMap,gMap);
        int second = g2(arr,0,arr.length-1,fMap,gMap);
        return Math.max(first,second);
    }

    //傻缓存做法
    //在区间[L....R]上先手先拿牌
    public static int f2(int[] arr, int L, int R,int[][] fMap,int[][] gMap){
        if(fMap[L][R]!=-1){
            return fMap[L][R];
        }
        int ans = 0;
        if(L==R){
            //只剩下一张牌,那只有先手拿到
           ans =  arr[R];
        }else {
            //否则有两种情况
            //先手拿走左边第一张牌
            int p1 = arr[L] + g2(arr,L+1,R,fMap,gMap);
            //第二种选择,先手拿走最右边的第一张牌
            int p2 = arr[R] + g2(arr,L,R-1,fMap,gMap);
            ans = Math.max(p1,p2);
        }
        //既然是先手做决定那肯定是拿到两个选择中最大的那个
        fMap[L][R] = ans;
        return ans;
    }

    //后手拿牌---先手先拿牌,先手拿完牌之后--后手就做了先手
    public static int g2(int[] arr, int L, int R,int[][] fMap,int[][] gMap){
        if(gMap[L][R]!=-1){
            return gMap[L][R];
        }
        int ans = 0;
        if(L!=R){
            //以下对于拿牌,还是右两种选择
            //第一种选择,先手拿完最左边的牌之后,后手在拿
            int p1 = f2(arr,L+1,R,fMap,gMap);
            //第二种选择,先手拿走最右边的牌之后,后手在拿
            int p2 = f2(arr,L,R-1,fMap,gMap);
            ans = Math.min(p1,p2);
        }
        gMap[L][R] = ans;
        return ans;//后手拿的牌是先手和后手拿的牌中的最小值
    }

    //改成动态规划
    public static int ways3(int[] arr){
        if(arr.length ==0||arr==null){
            return 0;
        }
        int N = arr.length;
        int[][] fMap = new int[N][N];
        int[][] gMap = new int[N][N];
        //先将对角线补齐
        for(int i =0;i<N;++i){
            fMap[i][i] = arr[i];
        }
        //gMap的对角线都是0,所以不用更新
        //列要从1开始--因为0已经被填过了
        //填右上三角的每一条对角线--处理中间那条
        for(int startCol = 1;startCol<N;++startCol){
            int L = 0;
            int R = startCol;//列每一次都要更新
            //列永远大于行的,如果列不越界,行永远也不会越界的
            //所以只判断列有没有越界
            while(R< N){
                 fMap[L][R] = Math.max(arr[L] + gMap[L+1][R],arr[R] + gMap[L][R-1]);
                 gMap[L][R] = Math.min(fMap[L+1][R],fMap[L][R-1]);
                 L++;
                 R++;
            }
        }
        return Math.max(fMap[0][N-1],gMap[0][N-1]);
    }

    public static void main(String[] args) {
        int[] arr = {5,7,4,5,8,1};
        System.out.println(ways1(arr));
        System.out.println(ways2(arr));
        System.out.println(ways3(arr));

    }

}
